package sun.scheduler.core;

import sun.scheduler.core.job.DummyJob;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import javax.swing.text.html.HTMLDocument;
import sun.scheduler.core.ScheduleGraph.StartTimes;
import sun.scheduler.core.job.Job;
import sun.scheduler.core.job.Job.CurveState;
import sun.scheduler.core.job.RoundingInfo;
import sun.scheduler.core.job.SchedulingInfo;
import sun.scheduler.core.resource.Resource;
import sun.scheduler.core.resource.ResourceProfile;
import sun.scheduler.core.resource.ResourceProfileMap;
import sun.scheduler.core.scheduling.ResourceScheduler;
import sun.scheduler.util.graph.Edge;
import sun.scheduler.util.graph.EdgeIterator;
import sun.scheduler.util.graph.Graph;
import sun.scheduler.util.graph.Node;
import sun.scheduler.util.graph.algorithm.maxflow.EdgeFlow;

/**
 * A Graph that represents a PERT diagram, which asumes a start and a end node
 * which have to be the first and last elements in a topologic order. It
 * provides methods for creating a subgraph which contains only critical edges
 * as defined by the critical path method.
 *
 * @see Graph
 * @see Schedule
 * @see Job
 * @author May, MFJ
 */
public class ScheduleGraph extends Graph<StartTimes, Job>
{

    /**
     * Primitive class implementing a pair of {@code int}s representing an edge
     * in the graph
     */
    private class Pair
    {

        public int start, end;

        public Pair(int start, int end)
        {
            this.start = start;
            this.end = end;
        }

    }
    /**
     * defines which kind of info are used right now
     */
    private Job.CurveState cState;
    /**
     * List of all jobs as {@code JobInfo}
     */
    private ArrayList<Job> jobs;

    /*
     * Id's of the source and target node 
     */
    private int sourceId, targetId;
    /*
     * target node
     */
    private Node<StartTimes, Job> target;
    /*
     *
     */
    private int modCount = 0;
    /**
     * {@code HashMap<JobInfo, Pair>} jontaining all jobs and paires
     * representing start and endnodeid
     */
    private HashMap<Job, Pair> jEdges;
    private ResourceProfileMap rProfiles;

    /**
     * Instantiates an empty {@link ScheduleGraph}. This constructor may be used
     * for testing purposes
     *
     * @param capacity
     */
    public ScheduleGraph(int capacity)
    {
        super(capacity);
    }

    /**
     * Initializes the ScheduleGraph
     *
     * @param jobs containing different informations
     */
    public ScheduleGraph(ArrayList<Job> jobs)
    {
        /*
         * init graph with duoble number of jobs (start and endnode for each
         * job)
         */
        super(jobs.size() * 2 + 10);
        this.cState = Job.CurveState.LTCT;
        this.jobs = jobs;

        int size = jobs.size() * 2 + 10;
        for (int i = 0; i < size; i++)
            addNode(new StartTimes());

        jEdges = new HashMap<Job, Pair>(size);
        createNetwork();
        initializeGraph();

        rProfiles = new ResourceProfileMap(jobs.size());
        for (Job job : jobs)
            rProfiles.set(job.resource, new ResourceProfile(job.resource));
    }

    /**
     * Gets the modified processes.
     *
     * @return the processes
     */
    public ArrayList<Job> getJobs()
    {
        return jobs;
    }

    /**
     * gets the state that defines which kind of informations are used in
     * JobInfo right now
     *
     * @return state of this graph
     */
    public CurveState getCurveState()
    {
        return cState;
    }

    /**
     * Gets the resource profiles used in this instance.
     * @return the resource profiles.
     */
    public ResourceProfileMap getResourceProfiles()
    {
        return rProfiles;
    }

    
    
    /**
     * sets the state that defines which kind of informations are used in
     * JobInfo right now
     *
     * @param cState state of this graph
     */
    public void setCurveState(CurveState cState)
    {
        this.cState = cState;
    }

    /**
     * Initializes HashMap representing the Network of jobs and dummyjobs
     */
    private void createNetwork()
    {
        int endId = jobs.size() * 2 + 9;
        for (Job job : jobs)
        {
            jEdges.put(job, new Pair(jobs.size() + job.jobId + 1, job.jobId));
            for (Integer pred : job.getPredecessors())
            {
                jobs.get(pred - 1).addSuccessor(job.jobId);
                DummyJob d = new DummyJob(jobs.size() + job.jobId + 1);
                jEdges.put(d, new Pair(pred, jobs.size() + job.jobId + 1));
            }
            if (job.getPredecessors().isEmpty())
                jEdges.get(job).start = 0;
        }
        for (Job job : jobs)
        {
            if (job instanceof DummyJob)
                break;
            if (job.getSuccessors().isEmpty())
                if (endId == -1)
                    endId = job.jobId;
                else
                    jEdges.put(new DummyJob(endId), new Pair(job.jobId, endId));
        }
    }

    /**
     * adding all key value pairs of jEdges to this as edges
     */
    private void initializeGraph()
    {
        for (Job job : jEdges.keySet())
        {
            Pair p = jEdges.get(job);
            this.addEdge(p.start, p.end, job);
        }
        sourceId = topologicOrder().get(0).id();
        target = topologicOrder().get(topologicOrder().size() - 1);
        targetId = target.id();
    }

    /**
     * Gets the target node.
     *
     * @return the target node.
     */
    public Node<StartTimes, Job> getTarget()
    {
        return target;
    }

    /**
     * Rounds all jobs of this {@link ScheduleGraph} instance.
     */
    public void round()
    {
        if (Job.CurveState.Rounding != cState)
            throw new IllegalStateException("Rounding is only allowed in Roundingstate");
        for (Job j : jobs)
        {
            if (j instanceof DummyJob)
                break;
            RoundingInfo r = (RoundingInfo) j.getProcess(cState);
            r.round();
        }
        
        updateJobTimeParameters();
    }

    /**
     * Scheules all job of {@link ScheduleGraph} instance using the {@link ResourceScheduler}.
     */
    public void schedule()
    {
        if (Job.CurveState.Scheduling != cState)
            throw new IllegalStateException("Scheduling is only allowed in Schedulingstate");

        for (Job j : jobs)
        {
            if (j instanceof DummyJob)
                break;
            SchedulingInfo s = (SchedulingInfo) j.getProcess(cState);
            s.updateStartTimes();
        }

        rProfiles.clear();
        ResourceScheduler scheduler = new ResourceScheduler(this, rProfiles);
        scheduler.run();
    }

    private void checkSTIds()
    {
        if (modCount != getEdgeModCount())
        {
            ArrayList<Node<StartTimes, Job>> tO = topologicOrder();
            sourceId = tO.get(0).id();
            targetId = tO.get(tO.size() - 1).id();
            target = getNode(targetId);
            modCount = getEdgeModCount();
        }
    }

    /**
     * Id of the source node. Which is the first node in topolocic order.
     *
     * @return id of the source node which ranges from zero to the number of
     * nodes minus one.
     */
    public int getSourceId()
    {
        checkSTIds();
        return sourceId;
    }

    /**
     * Id of the target node. Which is the last node in topolocic order.
     *
     * @return id of the target node which ranges from zero to the number of
     * nodes minus one.
     */
    public int getTargetId()
    {
        checkSTIds();
        return targetId;
    }

    /**
     * Updates the EST and LST for each {@link job} given that length of some
     * jobs have changed.
     */
    public void updateJobTimeParameters()
    {
        updateNodeStartTimes();
        EdgeIterator<StartTimes, Job> edgeIterator = getEdgeIterator();
        while (edgeIterator.hasNext())
        {
            Edge<StartTimes, Job> next = edgeIterator.next();
            Job job = next.getData();

            job.setEarliestStartTime(cState, next.getStart().getData().earliestStartTime);
            job.setLatestEndTime(cState, next.getEnd().getData().earliestStartTime);
        }
    }

    /**
     * Checks if the given {@link Job} represented by the specified {@link Edge}
     * (i,j) is critical. A {@link Job} is critical if it is an element of the
     * longest Path conntecting the source and target nodes of this
     * PERT-diagram: i.e. if j.latestStartTime - i.earliestStartTime =
     * (i,j).duration.
     *
     * @param edge the edge to check.
     * @return {@code edge.getEnd().getData().latestStartTime
     * - edge.getStart().getData().earliestStartTime
     * == edge.getData().getDuration()}
     */
    public boolean isCritical(Edge<StartTimes, Job> edge)
    {
        // LSj - ESi = pij
        return edge.getEnd().getData().latestStartTime
                - edge.getStart().getData().earliestStartTime
                == edge.getData().getDuration(cState);
    }

    /**
     * Updates the state of this instance. Recomputes the {@link StartTime} for
     * each node in O(m) time. The Earliest start is defined as the earliest
     * start possible, hence the minimal time in which all Predessesors are
     * finished. The latest start is the latest start time possible in which the
     * project still executes in time.
     */
    public void updateNodeStartTimes()
    {
        updateEarliestStartTimes();
        updateLatestEndTimes();
    }

    /**
     * Updates the earliest start time for each node in this graph
     *
     * @return earliest end of whole project
     */
    public long updateEarliestStartTimes()
    {
        ArrayList<Node<StartTimes, Job>> topologicalOrder = topologicOrder();
        checkSTIds();

        // setUp EST for each node which is defined as the earliest start possible
        // whereby a job can only execute if all predessesors are finished:
        // EST_s := 0; EST_n+1 := min over EST of all predesessors + duration
        long latest = 0;
        for (int i = 0, n = topologicalOrder.size(); i < n; i++)
        {
            Node<StartTimes, Job> node = topologicalOrder.get(i);
            // get max i.EST + (i,node).duration for all ingoing edges
            long maxStartTime = 0;
            for (Edge<StartTimes, Job> edge : node.getInEdges())
            {
                long nextEST = edge.getStart().getData().earliestStartTime;
                nextEST += edge.getData().getDuration(cState);
                if (nextEST > maxStartTime)
                    maxStartTime = nextEST;
            }

            //set earliest startTime to maxStartTime
            node.getData().earliestStartTime = maxStartTime;
            latest = Math.max(maxStartTime, latest);
        }

        return latest;
    }

    /**
     * Updates the latest start times of each node in this graph
     *
     * @return latest start of whole project should be normaly zero
     */
    public long updateLatestEndTimes()
    {
        // setUp LST for each node which is defined as the lates start possible
        // whereby a job can only execute later if the schedule would still
        // finish in time:
        target.getData().latestStartTime = target.getData().earliestStartTime;

        long earliest = Long.MAX_VALUE;
        for (int i = topologicOrder().size() - 2; i >= 0; i--)
        {
            Node<StartTimes, Job> node = topologicOrder().get(i);
            // get min j.LST - (node,j).duration for all outgoing edges
            long minEndTime = Long.MAX_VALUE;
            for (Edge<StartTimes, Job> edge : node.getOutEdges())
            {
                long nextLST = edge.getEnd().getData().latestStartTime;
                nextLST -= edge.getData().getDuration(cState);
                if (nextLST < minEndTime)
                    minEndTime = nextLST;
            }

            //set latest startTime to minEndTime
            node.getData().latestStartTime = minEndTime;
            earliest = Math.min(minEndTime, earliest);
        }

        return earliest;
    }

    /**
     * getter for the JobInfo instance with the specified id
     *
     * @param id of the JobInfo
     * @return {@code JobInfo} instance with specified id
     */
    public Job getJob(int id)
    {
        return jobs.get(id - 1);
    }

    /**
     * Increases the earliest start time of thisjob and updates the start times
     * of all succsessor jobs.
     *
     * @param job the job which starttime is to increase
     * @param newEST the new bigger earliest startime of the job
     * @throws IllegalArgumentException if the nw EST is smaller then the
     * current EST: {@code newEST < job.getEarliestStartTime(cState)}
     */
    public void increaseEarliestStartTime(Job job, long newEST)
    {
        job.setEarliestStartTime(cState, newEST);

        long delta = newEST + job.getDuration(cState) - job.getLatestEndTime(cState);
        if (delta <= 0)
            return;

        _updateStartTime(getNode(jEdges.get(job).start), newEST);
        updateLatestEndTimes();

        // increase/update job EST and LSE
        EdgeIterator<StartTimes, Job> edgeIterator = getEdgeIterator();
        while (edgeIterator.hasNext())
        {
            Edge<StartTimes, Job> next = edgeIterator.next();
            Job j = next.getData();

            if (next.getStart().getData().earliestStartTime > j.getEarliestStartTime(cState))
                j.setEarliestStartTime(cState, next.getStart().getData().earliestStartTime);
            if (next.getEnd().getData().earliestStartTime > j.getLatestEndTime(cState))
                j.setLatestEndTime(cState, next.getEnd().getData().earliestStartTime);
        }
    }

    private void _updateStartTime(Node<StartTimes, Job> node, long newEST)
    {
        if (newEST <= node.getData().earliestStartTime)
            return;

        node.getData().earliestStartTime = newEST;
        for (Edge<StartTimes, Job> outEdge : node.getOutEdges())
            _updateStartTime(outEdge.getEnd(), newEST + outEdge.getData().getDuration(cState) + 1);

    }

    public Iterator<Job> jobIterator()
    {
        return jobs.iterator();
    }

    /**
     * Some {@link Node} data content which is used for the critical path
     * method.
     */
    public class StartTimes
    {

        protected long latestStartTime;
        protected long earliestStartTime;

        /**
         * Gets the earliest starttime, which is defined as the time at which
         * the {@link Job}'s of all predesessors are completed. Therefore the
         * earliest starttime is the smalest time at which all utgion jobs can
         * start.
         *
         * @return the earliest starttime
         */
        public long getEarliestStartTime()
        {
            return earliestStartTime;
        }

        /**
         * Gets the latest starttime, which is defined as the time at which the {@link Job}
         * may start without changing the duration of the overall duration.
         *
         * @return the latest starttime
         */
        public long getLatestStartTime()
        {
            return latestStartTime;
        }

        @Override
        public String toString()
        {
            return "ES: " + earliestStartTime + " LS: " + latestStartTime;
        }

        public void setLatestStartTime(long latestStartTime)
        {
            this.latestStartTime = latestStartTime;
        }

        public void setEarliestStartTime(long earliestStarTime)
        {
            this.earliestStartTime = earliestStarTime;
        }

    }
}
